package leetcode.editor.cn;

//给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10n 。 
//
// 示例: 
//
// 输入: 2
//输出: 91 
//解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外，在 [0,100) 区间内的所有数字。
// 
// Related Topics 数学 动态规划 回溯 👍 171 👎 0

//Java：计算各个位数不同的数字个数
public class CountNumbersWithUniqueDigits_357{
    public static void main(String[] args) {
        Solution solution = new CountNumbersWithUniqueDigits_357().new Solution();
        // TO TEST
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        if(n==0) return 1;
        int count=9;
        for (int i = 0; i < n-1; i++) {
            count*=(9-i);
        }
        return count+countNumbersWithUniqueDigits(n-1);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
